package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/1
 * @Description: 选择排序
 * @version: 1.0
 */
public class ChooseSort {

    /*
     * 时间复杂度: 最好O(n^2)  最环O(n^2)  平均O(n^2)
     * 空间复杂度: O(1)
     */
    public static int[] chooseSort(int[] arr) {
        //一共需要选择的次数: arr.length-1
        //假设最后一个元素为最大值，即最大值索引为arr.length-1，每选择一次，最大索引递减
        for (int right = arr.length - 1; right > 0; right--) {
            int maxIndex = right;
            for (int i = 0; i < maxIndex; i++) {
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            //交换元素
            if (right != maxIndex) {
                int tem = arr[right];
                arr[right] = arr[maxIndex];
                arr[maxIndex] = tem;
            }
        }
        return arr;
    }
}
